#include "algorithm_annealing.h"

/** Ulozeni energie reseni do vysledku.
 * \param energy energie reseni
 */
void HurleyCooler::Energy(int energy) {
	energies[pos++] = energy;
}

/** Na zaklade vysledku reseni z aktualniho kroku urci novou teplotu.
 */
void HurleyCooler::Update() {
	double sum = 0, squares = 0;
	for (int i = 0; i < loop_count; ++i) {
		sum += energies[i];
		squares += SQR(energies[i]);
	}
	double psi = loop_count * squares - SQR(sum) + 0.5;
	/* score of the last round */
	double round_score = sqrt(psi) / loop_count;
	double delta = 0.1;
	/* new temperature */
	temperature = temperature / (1 + (log(1 + delta) * temperature) / (3 * round_score));
	pos = 0;
}


/** Prejde od aktualniho reseni do "lepsiho" sousedniho reseni.
 * \param calls prirazeni frekvenci, ktere ma byt zmeneno
 * \param better lepsi sousedni reseni
 */
void AnnealingSolution::MoveTo(int * calls, AnnealingSolution & better) {
	int * tmp = violating;
	violating = better.violating;
	better.violating = tmp;
	std::swap(count, better.count);
	std::swap(energy, better.energy);
	calls[better.chosen] = better.frequency;
}


/** Vytvori souseda aktualniho reseni pomoci metody omezeneho nahodneho sousedstvi.
 * \param base aktualni reseni
 * \param neighbour soused, vystupni parametr
 */
void AnnealingAlgorithm::GetNeighbour(AnnealingSolution & base, AnnealingSolution & neighbour) {
	/* choose a call from the violating list and a new frequency for it */
	neighbour.chosen = base.violating[rand() % base.count];
	do {
		neighbour.frequency = rand() % frequencies + 1;
	}
	while (neighbour.frequency == area->calls[neighbour.chosen]);
	//options->Log() << "Vybrany soused: " << neighbour.chosen << "(" << area->calls[neighbour.chosen] << "->" << neighbour.frequency << ")" << std::endl;
	/* count the new energy */
	int cell = area->findCell(neighbour.chosen);
	/* copy the violating ones */
	for (neighbour.count = 0; neighbour.count < base.count; ++neighbour.count) {
		neighbour.violating[neighbour.count] = base.violating[neighbour.count];
	}
	/* perform the change */
	int oldfrequency = area->calls[neighbour.chosen];
	area->calls[neighbour.chosen] = neighbour.frequency;
	CountEnergy(neighbour);
	/* return it back */
	area->calls[neighbour.chosen] = oldfrequency;
}

/** Urci zda je nove reseni lepsi nez aktualni v zavislosti na jejich kvalite a aktualni teplota.
 * \param newer energie noveho reseni
 * \param old energie aktualniho reseni
 * \param temperature teplota latky, cim je vetsi, tim vetsi je sance prijmout horsi reseni
 */
bool AnnealingAlgorithm::IsBetter(int newer, int old, double temperature) {
	int delta = newer - old;
	if (delta < 0) return true; // newer energy is smaller
	else {
		// accept worser solution - to escape from local minima
		double r = (double)rand() / RAND_MAX;
		double prob = exp(-delta/temperature);
		if (r < prob) return true;
		else return false;
	}
}

/** Spocita energii reseni. Cim vetsi energie je, tim je reseni horsi.
 * \param solution reseni, je mu vyplnena energie
 */
void AnnealingAlgorithm::CountEnergy(AnnealingSolution & solution) {
	constraints->Clear();
	solution.energy = 0;
	// clear the violation mask
	for (int i = 0; i < area->size; ++i) {
		solution.violation_mask[i] = false;
	}
	/* mark as violating all the antenas, that are too close */
	for (int i = 0; i < solution.count; ++i) {
		bool violates = false;
		int cell = area->findCell(solution.violating[i]);
		//options->Log() << "Zkoumam " << solution.violating[i] << " Cell=" << cell + 1 << " (" << area->calls[solution.violating[i]] << ")";
		/* all neighbours */
		for (std::vector<int>::const_iterator n = area->cells[cell].constraints.begin();
			n != area->cells[cell].constraints.end(); ++n) {
			/* all neighbours' calls */
			int distance = area->frequencyDistance(cell, *n);
//			options->Log() << "| sousedni bunka:" << *n + 1 <<  ", vzdalenost: " << distance << " ";
			for (int call = area->cells[*n].index; call < area->cells[*n].index + area->cells[*n].demand; ++call) {
				if (call == solution.violating[i]) continue;
				if (abs(area->calls[solution.violating[i]] - area->calls[call]) < distance && !constraints->IsSet(call, solution.violating[i], true)) {
					//options->Log() << " poruseni: (" << *n + 1 << ":" << call << "=" << area->calls[call] << ")";
					solution.energy += distance - abs(area->calls[solution.violating[i]] - area->calls[call]);
					solution.violation_mask[call] = true;
					violates = true;
				}
			}
		}
		if (violates) {
			solution.violation_mask[solution.violating[i]] = true;
		}
//		options->Log() << std::endl;
	}
	solution.count = 0;
	for (int i = 0; i < area->size; ++i) {
		if (solution.violation_mask[i]) solution.violating[solution.count++] = i;
	}
}


/** Snizi pocet pouzitelnych frekvenci v reseni. Odebere nejvetsi frekvence, vsechny vysilace, jimz
 * byla tato frekvence prirazena jsou "preladeny" na nahodne zvolenou nizsi frekvenci.
 * \param solution reseni, ktere ma byt zmeneno
 */
void AnnealingAlgorithm::LowerFrequencies(AnnealingSolution & solution) {
	solution.count = 0;
	/* mark and reassign the ones with the highest frequency */
	for (int i = 0; i < area->size; ++i) {
		if (area->calls[i] == frequencies) {
			solution.violating[solution.count++] = i;
			area->calls[i] = (rand() % (frequencies - 1)) + 1; // assign new random frequency [1..frequencies-1]
		}
	}
	/* count the energy of the system and lower the number of the frequencies */
	CountEnergy(solution);
	--frequencies;
}

/** Nastavi pocatecni teplotu algoritmu tak, aby byl pomer prijatych reseni v jednom kroku algoritmu
 * nejmene accept_ratio.
 * \param best aktualni reseni
 * \param current pomocne reseni
 */
void AnnealingAlgorithm::SetStartingTemperature(AnnealingSolution & best, AnnealingSolution & current) {
	// raise the starting temperature until the acceptance ratio is higher than 0.9
	while (true) {
		int accepted = 0;
		for (int i = 0; i < cooler->LoopCount() && best.energy > 0; ++i) {
			GetNeighbour(best, current);
			if (IsBetter(current.energy, best.energy, cooler->Temperature())) {
				++accepted;
			}
		}
		if (accepted < options->accept_ratio * cooler->LoopCount()) {
			if (!cooler->DoubleTemperature()) {
				break;
			}
		}
		else {
			break;
		}
	}
}

/** Spusti algoritmus simulovaneho zihani na zadanou mapu.
 * Nejprve vytvori prvotni prirazeni podle zadaneho prvotniho algoritmu, pote vzdy odebere nejvyssi
 * frekvenci a v takovemto reseni se snazi minimalizovat energii na 0 pomoci algoritmu simulovaneho
 * zihani.
 * \return true, pokud se povedlo vytvorit korektni prirazeni frekvenci 
 */
bool AnnealingAlgorithm::Solve() {
	timer->start();
	/* run initial assignment algorithm (specified as my son) */
	Algorithm * initial = TestManager::GetAlgorithm(options->initial, options);
	if (!initial) {
		options->Log() << "Error: invalid initial algorithm!" << std::endl;
		return false;
	}
	initial->Set(area);
	if (!initial->Solve()) {
		options->Log() << "Error: initial algorithm assigned a bad assignment!" << std::endl;
		delete initial;
		return false;
	}
	options->Log() << "- initial algorithm (" << initial->GetDetail() << ") assigned: " << initial->Frequencies() << " frequencies in " << timer->lap() << " s." << std::endl
		<< "- starting simulated annealing for optimalization of the solution" << std::endl;
	frequencies = initial->Frequencies() + 1;
	delete initial;

	/* try to optimise it as much as I can
		- take out the highest frequency
		- run simulated annealing to assign the frequencies lower frequencies to them
	*/
	// create a cooler
	switch (options->cooling) {
		case Geometric:
			cooler = new GeometricCooler(options->alpha, (int)(options->loops * area->size));
			break;
		case Costa:
			cooler = new CostaCooler(options->alpha, (int)(options->loops * area->size));
			break;
		case Hurley:
			cooler = new HurleyCooler(options->alpha, (int)(options->loops * area->size));
			break;
	}

	AnnealingSolution best(area->size),	current(area->size);
	constraints = new ConstraintMask(area->size);
	// write out some text
	options->NewDisplay();
	options->Display(", Annealing: ");
	options->NewDisplay();
	options->Log() << "Frequency;Violations;Energy;;Temperatures (Best energies);" << std::endl;
	while (best.energy == 0) {
		/* reassign antenas with the highest frequency to a randomly chosen lower one
			and mark the antenas violating any of the constraint
			and count the energy of the system
		*/
		cooler->Start();
		area->save();
		LowerFrequencies(best);
		if (best.energy != 0) {
			SetStartingTemperature(best, current);
		}
		options->Log() << frequencies << ";" << best.count << ";" << best.energy << ";;";
		/* create 0 constraint violation assignment */
		while (cooler->Temperature() > options->end && best.energy != 0) {
			options->Display(IntToStr(frequencies) + ": t=" + DoubleToStr(cooler->Temperature()) + ", n=" + IntToStr(cooler->LoopCount()));
			// try to reassign frequencies and have no constraints broken
			options->Log() << cooler->Temperature() << " (" << best.energy << ");";
			for (int i = 0; i < cooler->LoopCount() && best.energy > 0; ++i) {
				// reassing to a random neighbour (pick a new random frequency for a violating antena) and create a neighbour violating array
				GetNeighbour(best, current);
				// store the generated energy
				cooler->Energy(current.energy);
				// if its energy is lower than the needed one than reassign;
				if (IsBetter(current.energy, best.energy, cooler->Temperature())) {
					best.MoveTo(area->calls, current);
				}
			}
			cooler->Update();
		}
		options->Log() << std::endl;
	}
	++frequencies; // last time it did not produce 0 energy
	area->load();
	options->Log() << "Simulovane zihani dopocitalo celkem za: " << timer->total() << std::endl;
	delete cooler;
	delete constraints;
	return true;
}
